/**
 * @file
 * @author dousha
 * @date 2020
 */

#include <stdbool.h>
#include "memory.h"

static MemoryManager *mm;

/**
 * 构建内存管理结构。
 *
 * @kernelOnly
 * 
 * @param start 初始地址
 * @param size 可用内存大小 (KiB)
 */
static void memory_deploy_structure(const void *start, uint32_t size, uint8_t flags) {
	mm = (MemoryManager *) start;
	mm->flags = flags;
	uint32_t offset = sizeof(MemoryManager);
	mm->start = (void *) (start + offset);
	mm->size = (size * 1024) - offset;
	mm->blocks = mm->start;
	mm->blocks->flags = 0;
	mm->blocks->length = mm->size - sizeof(MemoryBlock);
	mm->blocks->next = NIL;
	mm->blocks->base = memory_align(mm->start + offset + sizeof(MemoryBlock));
	mm->lastFreeBlock = mm->blocks;
}

/**
 * 初始化内存管理。
 *
 * @kernelOnly
 */
void memory_init() {
	const void *start = &_skylab_memory_start;
#ifdef USE_CCMRAM
	memory_deploy_structure(start, 64, MEMORY_USE_CCMRAM);
#else
	memory_deploy_structure(_task_heap_start, 32, 0);
#endif
}

/**
 * 按字节填充内存区域为固定的值。
 *
 * @param start 起始地址
 * @param len 长度
 * @param value 要填充的字节
 */
void memory_fill(void *start, uint32_t len, uint8_t value) {
	uint8_t *ptr = (uint8_t *) start;
	for (uint32_t i = 0; i < len; i++) {
		*ptr = value;
		++ptr;
	}
}

/**
 * 按字节复制内存内容。
 *
 * 如果复制区域有重叠，则可能会产生覆盖。使用 memory_move 避免这种情况。
 *
 * @param from 源地址
 * @param to 目的地址
 * @param len 长度
 */
void memory_copy(const void *from, void *restrict to, uint32_t len) {
	uint8_t byte;
	for (uint32_t i = 0; i < len; i++) {
		byte = ((uint8_t *) from)[i];
		((uint8_t *) to)[i] = byte;
	}
}

/**
 * 按字节复制内存内容。如果有重叠，则处理重叠区域。
 *
 * @param from 源地址
 * @param to 目的地址
 * @param len 长度
 */
void memory_move(const void *from, void *to, uint32_t len) {
	uint8_t byte;
	if (from > to) {
		for (uint32_t i = 0; i < len; i++) {
			byte = ((uint8_t *) from)[i];
			((uint8_t *) to)[i] = byte;
		}
	} else {
		for (uint32_t i = len; i > 0; i--) {
			byte = ((uint8_t *) from)[i - 1];
			((uint8_t *) to)[i - 1] = byte;
		}
	}
}

/**
 * 从空闲区块内分配空间。
 *
 * 这个函数将不检查分配大小是否合理，也不做空检查。
 *
 * @kernelOnly
 *
 * @param blk 空闲区块指针
 * @param size 请求分配的大小
 * @return 新分配的区块指针
 */
MemoryBlock *memory_allocate_block(MemoryBlock *blk, uint32_t size) {
	void *out = blk->base;
	void *nextBlockPos = memory_align(out + size);
	uint32_t length = (uint32_t) (nextBlockPos - out);
	// add a new block to be the last free block
	MemoryBlock *nextBlock = (MemoryBlock *) nextBlockPos;
	void *base = memory_align(nextBlockPos + sizeof(MemoryBlock));
	nextBlock->base = base;
	nextBlock->next = NIL;
	nextBlock->length = blk->length - length;
	nextBlock->flags = 0;
	// shrink and mark
	blk->length = length;
	blk->flags |= MEMORY_IN_USE;
	// TODO: Mark user blocks and system blocks
	// return the address
	return nextBlock;
}

/**
 * 分配内存空间。
 *
 * 这个操作非常耗费系统资源，不要频繁调用。
 * 见 `docs/practices.md` 关于内存管理的建议。
 *
 * 在没有可用空间的情况下，返回 `NIL`. 注意，内存碎片会导致
 * 大量内存不可用。
 *
 * 尝试访问分配内存之外的位置是未定义行为。
 *
 * @configControl `MEMORY_ALIGN_4B`
 * @configControl `NIL_IS_NULL`
 * @citeFile `docs/practices.md`
 *
 * @param size 要分配的内存大小
 * @return 指向可用位置的指针
 */
void *memory_allocate(uint32_t size) {
	// TODO: Maybe we can support overcommitting in the future
	if (size > mm->size - sizeof(MemoryBlock)) {
		return NIL;
	}
	if (mm->lastFreeBlock->length >= size + sizeof(MemoryBlock)) {
		// great
		MemoryBlock *nextBlock = memory_allocate_block(mm->lastFreeBlock, size);
		void *out = mm->lastFreeBlock->base;
		mm->lastFreeBlock->next = nextBlock;
		mm->lastFreeBlock = nextBlock;
		return out;
	} else {
		// sweep
		void *out = NIL;
		MemoryBlock *currentBlock = mm->blocks;
		while (currentBlock != NIL) {
			if (currentBlock->flags & MEMORY_IN_USE) {
				currentBlock = currentBlock->next;
				continue;
			}
			if (currentBlock->length >= size + sizeof(MemoryBlock)) {
				MemoryBlock *nextBlock = memory_allocate_block(currentBlock, size);
				nextBlock->next = currentBlock->next;
				currentBlock->next = nextBlock;
				out = currentBlock->base;
				break;
			}
			currentBlock = currentBlock->next;
		}
		return out;
	}
}

/**
 * 释放内存空间。
 *
 *
 * 这个操作非常耗费系统资源，不要频繁调用。
 * 见 `docs/practices.md` 关于内存管理的建议。
 *
 * 如果给定的指针不是从 `memory_allocate` 中获取的，
 * 那么什么事情都不会发生。但查找操作仍然会进行。
 *
 * 如果此函数从用户空间调用，而被释放的内存是系统内存，
 * 将会产生一个错误。视操作系统配置可能会导致任务被杀。
 *
 * 如果此函数尝试释放 `NIL` 或者释放已经释放的单元，
 * 将会产生一个错误。视操作系统配置可能会导致任务被杀。
 *
 * 由于大多数单片机没有内存控制单元，所以不可能做分页。
 * 如果用户程序频繁申请和释放内存，那么可能会产生非常多内存碎片。
 *
 * @configControl `KILL_ON_MEM_FAULT`
 * @citeFile `docs/practices.md`
 */
void memory_free(void *ptr) {
	if (ptr == NIL) {
#ifdef NIL_FREE_IS_VIOLATION
		memory_handle_access_fault(NIL_FREE);
#endif
		return;
	}
	MemoryBlock *lastBlock = NIL;
	MemoryBlock *currentBlock = mm->blocks;
	bool foundBlock = false;
	while (currentBlock != NIL) {
		if (currentBlock->base == ptr) {
			foundBlock = true;
			// mark current block free
			if (currentBlock->flags & MEMORY_IN_USE) {
				currentBlock->flags &= (0xffu ^ MEMORY_IN_USE);
				if (currentBlock->next != NIL) {
					if (!(currentBlock->next->flags & MEMORY_IN_USE)) {
						// next block is free, merge
						currentBlock->length += currentBlock->next->length + sizeof(MemoryBlock);
						currentBlock->next = currentBlock->next->next;
					}
				}
				if (lastBlock != NIL) {
					if (!(lastBlock->flags & MEMORY_IN_USE)) {
						// last block is free, merge
						lastBlock->length += currentBlock->length + sizeof(MemoryBlock);
						lastBlock->next = currentBlock->next;
					}
				}
			} else {
#ifdef DOUBLE_FREE_IS_VIOLATION
				memory_handle_access_fault(DOUBLE_FREE);
#endif
			}
			break;
		} else {
			lastBlock = currentBlock;
			currentBlock = currentBlock->next;
		}
	}
	if (!foundBlock) {
#ifdef WILD_FREE_IS_VIOLATION
		memory_handle_access_fault(WILD_FREE);
#endif
	}
}

/**
 * 将给定地址向高地址对齐。
 *
 * @param ptr 地址
 * @return 对齐后的地址
 */
void *memory_align(const void *ptr) {
#ifdef MEMORY_ALIGN_4B
	intptr_t intptr = (const intptr_t) ptr;
	intptr = ((intptr + MEMORY_ALIGN_SIZE - 1) & -MEMORY_ALIGN_SIZE);
	return (void *) intptr;
#else
	return (void *) ptr;
#endif
}

/**
 * 分配内存空间。
 *
 * 这个操作非常耗费系统资源，不要频繁调用。
 * 见 `docs/practices.md` 关于内存管理的建议。
 *
 * 在没有可用空间的情况下，触发内存访问错误。
 * 注意，内存碎片会导致大量内存不可用。
 *
 * 尝试访问分配内存之外的位置是未定义行为。
 *
 * @configControl `MEMORY_ALIGN_4B`
 * @configControl `NIL_IS_NULL`
 * @citeFile `docs/practices.md`
 *
 * @param size 要分配的内存大小
 * @return 指向可用位置的指针
 */ 
const void *memory_allocate_or_fail(uint32_t size) {
	const void *result = memory_allocate(size);
	if (result == NIL) {
		memory_handle_access_fault(OUT_OF_MEMORY);
	}
	return result;
}

/**
 * 处理内存访问错误。
 *
 * @kernelOnly
 *
 * @param fault 错误类型
 */
void memory_handle_access_fault(MemoryFault fault) {
	// TODO: Handle faults properly
	for (;;) {
		__asm volatile ("nop");
	}
}
